class BSTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.index = 0; // 左子树元素个数
  }
}

class BSTree {
  constructor() {
    this.root = null;
    this._indexCounter = 1;
  }

  insert(value) {
    this.root = this._insert(this.root, value);
    this._updateIndices();
  }

  _insert(node, value) {
    if (!node) return new BSTNode(value);

    if (value <= node.value) {
      // 允许重复值，插入到左子树
      node.left = this._insert(node.left, value);
    } else {
      node.right = this._insert(node.right, value);
    }
    return node;
  }

  search(value) {
    const node = this._search(this.root, value);
    return node ? {node, index: node.index} : {node: null, index: -1};
  }

  _search(node, value, path = []) {
    if (!node) return null;
    
    // 记录当前节点到路径
    path.push(node);
    
    if (value < node.value) {
      return this._search(node.left, value, path);
    } else if (value > node.value) {
      return this._search(node.right, value, path);
    } else {
      // 找到匹配节点，处理搜索路径
      TreeVisualizer.processSearchPath(path);
      return { node, path };
    }
  }


  // 计算左子树元素个数
  _countLeftSubtree(node) {
    if (!node) return 0;
    return this._countLeftSubtree(node.left) + 
           this._countLeftSubtree(node.right) + 1;
  }

  // 更新索引
  _updateIndices(node) {
    if (!node) return 0;
    
    node.index = this._countLeftSubtree(node.left);
    this._updateIndices(node.left);
    this._updateIndices(node.right);
    
    return node.index;
  }

  // 中序遍历
  ascend() {
    const result = [];
    this._inOrder(this.root, result);
    return result;
  }

  _inOrder(node, result) {
    if (!node) return;
    this._inOrder(node.left, result);
    result.push(node.value);
    this._inOrder(node.right, result);
  }

  // 层级遍历
  levelOrder() {
    const result = [];
    if (!this.root) return result;
    
    const queue = [this.root];
    while (queue.length > 0) {
      const node = queue.shift();
      result.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return result;
  }

  // 获取节点高度
  getHeight(node) {
    return node ? Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1 : 0;
  }

  // 获取平衡因子
  getBalanceFactor(node) {
    return this.getHeight(node.left) - this.getHeight(node.right);
  }

  // 判断是否为AVL树
  isAVL() {
    return this._isAVL(this.root);
  }

  _isAVL(node) {
    if (!node) return true;

    const balance = this.getBalanceFactor(node);
    if (Math.abs(balance) > 1) return false;

    return this._isAVL(node.left) && this._isAVL(node.right);
  }

  // 根据BST生成AVL树
  toAVLTree() {
    const avlTree = new AVLTree(null);
    const values = this.ascend();
    for (const value of values) {
      avlTree.insert(value);
    }
    return avlTree;
  }
}


class AVLNode extends BSTNode {
  constructor(value) {
    super(value);
    this.height = 1;
  }
}

class AVLTree extends BSTree {
  constructor() {
    super();
  }
  // 更新节点高度
  updateHeight(node) {
    node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
  }

  // 获取平衡因子
  getBalanceFactor(node) {
    return this.getHeight(node.left) - this.getHeight(node.right);
  }

  // 右旋转
  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;

    x.right = y;
    y.left = T2;

    this.updateHeight(y);
    this.updateHeight(x);

    return x;
  }

  // 左旋转
  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;

    y.left = x;
    x.right = T2;

    this.updateHeight(x);
    this.updateHeight(y);

    return y;
  }

  // 重写插入方法以支持平衡
  insert(value) {
    this.root = this._insert(this.root, value);
    this._updateIndices();
    TreeVisualizer.drawTree(this);
  }

  _insert(node, value) {
    if (!node) return new AVLNode(value);

    if (value <= node.value) {
      node.left = this._insert(node.left, value);
    } else {
      node.right = this._insert(node.right, value);
    }

    // 更新高度
    this.updateHeight(node);
    
    // 获取平衡因子
    const balance = this.getBalanceFactor(node);

    // 左左情况
    if (balance > 1 && value <= node.left.value) {
      return this.rotateRight(node);
    }

    // 右右情况
    if (balance < -1 && value > node.right.value) {
      return this.rotateLeft(node);
    }

    // 左右情况
    if (balance > 1 && value > node.left.value) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }

    // 右左情况
    if (balance < -1 && value <= node.right.value) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }

    return node;
  }

  // 更新层级索引
  _updateIndices() {
    this._updateIndex(this.root);
  }

  _updateIndex(node) {
    if (!node) return 0;
    
    // 计算左子树节点总数
    node.index = this._size(node.left);
    this._updateIndex(node.left);
    this._updateIndex(node.right);
    
    return node.index;
  }

  // 查找最小节点
  _findMin(node) {
    while (node && node.left) {
      node = node.left;
    }
    return node;
  }

  // 删除方法
  delete(value) {
    this.root = this._delete(this.root, value);
    this._updateIndices();
    TreeVisualizer.drawTree(this);
  }

  _delete(node, value) {
    if (!node) return null;

    if (value < node.value) {
      node.left = this._delete(node.left, value);
    } else if (value > node.value) {
      node.right = this._delete(node.right, value);
    } else {
      // 情况①：被删除节点是叶子节点
      if (!node.left && !node.right) {
        return null;
      }
      // 情况②：被删除节点只有一个子树
      else if (!node.left) {
        node = node.right;
      } else if (!node.right) {
        node = node.left;
      }
      // 情况③：被删除节点有两个子树
      else {
        // 找到右子树的最小节点
        const minNode = this._findMin(node.right);
        // 用最小节点的值替换当前节点
        node.value = minNode.value;
        // 删除右子树中的最小节点
        node.right = this._delete(node.right, minNode.value);
      }
    }

    if (!node) return null;

    // 更新高度
    this.updateHeight(node);

    // 平衡处理
    const balance = this.getBalanceFactor(node);

    // 左左情况
    if (balance > 1 && this.getBalanceFactor(node.left) >= 0) {
      return this.rotateRight(node);
    }

    // 右右情况
    if (balance < -1 && this.getBalanceFactor(node.right) <= 0) {
      return this.rotateLeft(node);
    }

    // 左右情况
    if (balance > 1 && this.getBalanceFactor(node.left) < 0) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }

    // 右左情况
    if (balance < -1 && this.getBalanceFactor(node.right) > 0) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }

    return node;
  }


  // 按索引搜索节点，时间复杂度O(logn)
  indexSearch(index) {
    return this._indexSearch(this.root, index);
  }

  _indexSearch(node, rank, path = []) {
    if (!node) return null;
    
    if (rank <= 0 || rank > this.size()) {
      return null;
    }
    
    // 记录当前节点到路径
    path.push(node);
    
    if (rank === node.index + 1) {
      // 找到目标节点，处理搜索路径
      TreeVisualizer.processSearchPath(path);
      return node;
    } else if (rank <= node.index) {
      return this._indexSearch(node.left, rank, path);
    } else {
      return this._indexSearch(node.right, rank - (node.index + 1), path);
    }
  }

  // 获取树的大小
  size() {
    return this._size(this.root);
  }

  _size(node) {
    if (!node) return 0;
    return 1 + this._size(node.left) + this._size(node.right);
  }

  // 按索引删除节点
  indexDelete(rank) {
    if (rank < 1 || rank > this.size()) {
      throw new Error(`Invalid rank: ${rank}. Must be between 1 and ${this.size()}`);
    }
    
    const node = this.indexSearch(rank);
    if (!node) {
      throw new Error(`Node not found for rank: ${rank}`);
    }
    
    // 直接使用_delete方法删除节点
    this.root = this._delete(this.root, node.value);
    this._updateIndices();
    TreeVisualizer.drawTree(this);
    return true;
  }

  // 获取树的大小
  size() {
    return this._size(this.root);
  }

  _size(node) {
    if (!node) return 0;
    return 1 + this._size(node.left) + this._size(node.right);
  }

  // 按索引删除节点
  indexDelete(rank) {
    if (rank < 1 || rank > this.size()) {
      throw new Error(`Invalid rank: ${rank}. Must be between 1 and ${this.size()}`);
    }
    
    const node = this.indexSearch(rank);
    if (!node) {
      throw new Error(`Node not found for rank: ${rank}`);
    }
    
    // 直接使用_delete方法删除节点
    this.root = this._delete(this.root, node.value);
    this._updateIndices();
    if (this.visualizer) {
      this.visualizer.drawTree(this);
    }
    return true;
  }
}
